package tree;

/**
 * @author: june
 * @date: 2023/7/19
 *
 * 235. 二叉搜索树的最近公共祖先
 *
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
 * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 **/

public class LowestCommonAncestor_235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 其实都不需要这个终止条件，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。
        // 也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。
        if (root == null) {
            return root;
        }

        // 如果p、q的值都比root的值要大，那么lca应该在root的右边，所以遍历root的右子树
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);

        }
        // 如果p、q的值都比root的值要小，那么lca应该在root的左边，所以遍历root的左子树
        else if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // 如果root的值在p、q之间，则符合要求
        else {
            return root;
        }
    }
}
